Batch 2 - Class 273 - Pool Testing
Zoom: send meeting Id and password
Start recording
Preclass Exercise:
Rope around the world puzzle (Credit: William Whiston 1667-1752)
Take a tennis ball, and choose one of its equators. How much longer would you have to make the rope so that it is one foot from the surface of the tennis ball at all points?
What if we took the equator of earth. How much longer would we have to make the rope so that it is one foot from the surface of the earth at all points?
Let kids guess the answers to each.
Answer: In both cases the answer is about 6.28 ft (2 pi) - a surprising conclusion given that most people expect the earth answer to be much higher.
Attendance: Raghav, Aneesh, Kabir, Advay, Shikhar, Ayush, Vivaan, Rhea Chadha, Ryan Chadha, Rohan, Siddanth, Yatharth, Mihir, Dhriti, Anika, Aarkin, Shubh, Vansh, Tarush, Adyant, Ishita, Aarushi, Harshiet
Class Notes:
Wild Tic-tac-toe
Wild tic-tic-toe is like normal tic-tac-toe except that a player can choose to play X or O on each of their turns. If a player is able to make three-in-a-row by doing so, they win. Think about who wins and what the winning strategy might be.
- Answer: First player wins. https://www.futurelearn.com/info/courses/recreational-math/0/steps/43532
Pool Testing
During the Covid pandemic, initially there was a shortage of testing kits. How can we apply mass screening with limited number of tests
- Students should be able to get to an idea of pool-testing on prompting. Essentially, test multiple people using a single test kit. If the test if positive, we know someone in the pool is infected, otherwise all are clear
- Lets look at some examples, for students to understand what a positive of negative pool test implies. Who amongst the following groups might be infected?
- What would be the trade-off to choosing the pool size?
- If its too large (say, 1 million) then we have to do a lot of follow up tests to determine who exactly is infected.
- If its too small, we are consuming a lot of tests
Our goal is to find an infected person using as few tests as possible. We are given that exactly one person is infected.
- If there are 6 patients and exactly one is infected, what is the minimum number of tests?
- What if there are 7 patients? 8? 9?
- If you can do only 5 tests, what is the largest number of patient population you can test?
See if you can motivate a binary tree construct to this.
Now, lets change the problem a little bit. We are short of testing kits, but we also want to get this done quickly. So we do parallel tests. So you do all the pool tests simultaneously, and do not have the ability to use results of one test to feed the next one.
- If there are 6 patients and exactly one is infected, what is the minimum number of tests?
- What if there are 7 patients? 8? 9?
- If you can do only 5 tests, what is the largest number of patient population you can test?
See if you can motivate a binary number labeling construct to this, with each pool capturing wherever the 1s appear.
- The clumsy lab technician is known to spill one of the tests. How will you design your pool tests to still be able to determine who is infected.
- This has an interesting "redundant coding" - we dont have to do double the number of tests. If we still label the first patient as 0000, and one test can get spilled, then how many "1"s should other people have (at least 2). How many of those combinations exist (4C2 = 6). Now we can't have a coding with 3 "1"s (in case one spills, we will be left with 2), but we can have another one with 4 "1"s. So we can measure 8 people with 4 tests! Think about what happens if any one test below (say Test 1) fails.
.png)
Homework Problem:
What if multiple people are infected? Say exactly two people? How would you solve the above problems? What if exactly 3 people were infected? What if an unknown number of people were infected?
- Note that in the worst case, you may have to land up testing everyone, but you can perhaps save probabilistically. If the density increases a lot, then you are better off just testing everyone individually - the tree approach there would lead to 2^n tests.
References:
https://docs.google.com/presentation/d/1zdxgedTbQh6i3hstGfJbQ0bsDHXf4xPAEXP7JuB-A58/